算法-二分查找详解[多语言实现]
二分查找(Binary Search)是一种高效的查找算法,常用于有序数组或序列。根据循环条件和区间定义的不同,二分查找可以有多种写法,主要包括以下四种:
1. 闭区间 [left,right]
搜索区间是闭区间 [left, right]
代码模板:
c++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| int binary_serach(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while (left <= right) { int middle = left + (right - left) / 2; if (nums[middle] == target) { return middle; } else if (nums[middle] < target) { left = middle + 1; } else { right = middle - 1; } } return -1; }
|
JavaScript:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| var binary_search = function(nums, target) { let left = 0; let right = nums.length - 1; while(left <= right){ let middle = Math.floor((left + right) / 2); if(nums[middle] === target){ return middle; }else if(nums[middle] < target){ left = middle + 1; }else{ right = middle - 1; } } return -1; };
|
go:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| func binary_search(nums []int, target int) int { left, right := 0, len(nums)-1 for left <= right { middle := left + (right-left)/2 if nums[middle] == target { return middle } else if nums[middle] < target { left = middle + 1 } else { right = middle - 1 } } return -1 }
|
python:
1 2 3 4 5 6 7 8 9 10 11
| def binary_search(nums, target): left, right = 0, len(nums) - 1 while left <= right: middle = left + (right - left) // 2 if nums[middle] == target: return middle elif nums[middle] < target: left = middle + 1 else: right = middle - 1 return -1
|
特点:
- 循环条件是
left <= right
。// 为什么是小于等于,因为当left=right的时候,还有一个元素没有进行比较 - 更新指针时需要调整
left = middle + 1
或 right = middle - 1
。 - 适用于大多数查找场景。
- 目标值未找到:此时,
left
和 right
会交错,left
可能会越过 right
,即 left
会比 right
大。// 我的理解:指针交错
2. 左闭右开 [left,right)
搜索区间为左闭右开 [left, right)
代码模板:
c++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| int binary_serach(vector<int>& nums, int target) { int left = 0; int right = nums.size(); while (left < right) { int middle = left + (right - left) / 2; if (nums[middle] == target) { return middle; } else if (nums[middle] < target) { left = middle + 1; } else { right = middle; } } return -1; }
|
JavaScript:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| var binary_search = function(nums, target) { let left = 0; let right = nums.length; while(left < right){ let middle = Math.floor((left + right) / 2); if(nums[middle] === target){ return middle; }else if(nums[middle] < target){ left = middle + 1; }else{ right = middle; } } return -1; };
|
go:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| func binary_search(nums []int, target int) int { left, right := 0, len(nums) for left < right { middle := left + (right-left)/2 if nums[middle] == target { return middle } else if nums[middle] < target { left = middle + 1 } else { right = middle } } return -1 }
|
python:
1 2 3 4 5 6 7 8 9 10 11
| def binary_search(nums, target): left, right = 0, len(nums) while left < right: middle = left + (right - left) // 2 if nums[middle] == target: return middle elif nums[middle] < target: left = middle + 1 else: right = middle return -1
|
特点:
- 循环条件是
left < right
。 - 更新指针时,
left = middle + 1
或 right = middle
。 - 更适合实现一些需要明确界限的算法(如快速插入位置)。
- 目标值未找到:此时,
left
会指向目标值应该插入的位置(即大于目标值的位置),right
会指向比目标值小的位置。// 我的理解:两个指针一起指在左边
3. 左开右闭 (left,right]
搜索区间为左开右闭 (left, right]
代码模板:
c++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| int binary_serach(vector<int>& nums, int target) { int left = -1; int right = nums.size() - 1; while (left < right) { int middle = left + (right - left + 1) / 2; if(nums[middle] == target) { return middle; } else if (nums[middle] < target) { left = middle; } else { right = middle - 1; } } return -1; }
|
JavaScript:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| var binary_search = function(nums, target) { let left = -1; let right = nums.length-1; while(left < right){ let middle = Math.ceil((left + right) / 2); if(nums[middle] === target){ return middle; }else if(nums[middle] < target){ left = middle; }else{ right = middle - 1; } } return -1; };
|
go:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| func binary_search(nums []int, target int) int { left, right := -1, len(nums)-1 for left < right { middle := left + (right-left+1)/2 if nums[middle] == target { return middle } else if nums[middle] < target { left = middle } else { right = middle - 1 } } return -1 }
|
python:
1 2 3 4 5 6 7 8 9 10 11
| def binary_search(nums, target): left, right = -1, len(nums) - 1 while left < right: middle = left + (right - left + 1) // 2 if nums[middle] == target: return middle elif nums[middle] < target: left = middle else: right = middle - 1 return -1
|
特点:
- 循环条件是
left < right
。 - 更新指针时,
left = middle
或 right = middle - 1
。 - 通常需要调整初始值。
- 目标值未找到:此时,
left
会指向目标值应该插入的位置(即大于目标值的位置),right
会指向目标值应该插入的位置,或者是小于目标值的位置。// 我的理解:两个指针一起指在右边
4. 开区间 (left,right)
搜索区间为开区间 (left, right)
代码模板:
c++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| int binary_serach(vector<int>& nums, int target) { int left = -1; int right = nums.size(); while (left + 1 < right) { int middle = left + (right - left) / 2; if (nums[middle] == target) { return middle; } else if (nums[middle] < target) { left = middle; } else { right = middle; } } return -1; }
|
JavaScript:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| var binary_search = function(nums, target) { let left = -1; let right = nums.length; while(left+1 < right){ let middle = Math.floor((left + right) / 2); if(nums[middle] === target){ return middle; }else if(nums[middle] < target){ left = middle; }else{ right = middle; } } return -1; };
|
go:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| func binary_search(nums []int, target int) int { left, right := -1, len(nums) for left+1 < right { middle := left + (right-left)/2 if nums[middle] == target { return middle } else if nums[middle] < target { left = middle } else { right = middle } } return -1 }
|
python:
1 2 3 4 5 6 7 8 9 10 11
| def binary_search(nums, target): left, right = -1, len(nums) while left + 1 < right: middle = left + (right - left) // 2 if nums[middle] == target: return middle elif nums[middle] < target: left = middle else: right = middle return -1
|
特点:
- 循环条件是
left + 1 < right
。 - 更新指针时,
left = middle
或 right = middle
。 - 在某些特殊算法(如上下边界问题)中有用。
- 目标值未找到:此时,
left
和 right
都指向目标值应该插入的位置。// 我的理解:两个指针一左一右在两边,不交错
总结对比
区间类型 | 初始值 | 循环条件 | 指针更新 |
---|
闭区间[left,right] | left = 0, right = n-1 | left <= right | left = middle + 1 或 right = middle - 1 |
左闭右开[left,right) | left = 0, right = n | left < right | left = middle + 1 或 right = middle |
左开右闭 (left,right] | left = -1, right = n-1 | left < right | left = middle 或 right = middle - 1 |
开区间 (left,right) | left = -1, right = n | left + 1 < right | left = middle 或 right = middle |